package cn.nju.sirx.algorithm.sort;

/**
 * Merge sort.
 * 
 * @author SirX
 */
public class MergeSort implements ISort {

    @Override
    public <T extends Comparable<? super T>> void sort(T[] data) {
        sort(data, 0, data.length - 1);
    }

    private <T extends Comparable<? super T>> void sort(T[] data, int i, int j) {
        if (i == j)
            return;

        // divide
        int mid = (i + j) / 2;
        // sort
        sort(data, i, mid);
        sort(data, mid + 1, j);
        // merge
        Object[] tmp = new Object[j - i + 1];
        int p = i, q = mid + 1, t = 0;
        while (p <= mid && q <= j) {
            if (data[p].compareTo(data[q]) <= 0) {
                tmp[t++] = data[p++];
            } else {
                tmp[t++] = data[q++];
            }
        }
        if (p > mid) {
            while (q <= j) {
                tmp[t++] = data[q++];
            }
        } else if (q > j) {
            while (p <= mid) {
                tmp[t++] = data[p++];
            }
        }
        System.arraycopy(tmp, 0, data, i, tmp.length);
    }

}
